package com.sise.Tree;

import java.util.HashMap;

/**
 *      106. 从中序与后序遍历序列构造二叉树
 *
 *      中序遍历 inorder = [9,3,15,20,7]            左根右
 *      后序遍历 postorder = [9,15,7,20,3]          左右根
 *
 *      返回如下的二叉树：
 *
 *            3
 *           / \
 *          9  20
 *            /  \
 *           15   7
 */
public class _106_buildTree {

    private HashMap<Integer,Integer> indexMap = new HashMap<>();
    private int[] postOrder;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.postOrder = postorder;

        for (int i = 0; i < inorder.length; i++){
            indexMap.put(inorder[i], i);
        }

        return myBuildTree(0, inorder.length - 1, 0, postorder.length - 1);
    }

    // 这里没有在方法中 传递两个数组，而是将 postorder 写在全局参数中，只使用到了后序遍历，中序遍历的数组并不需要使用
    private TreeNode myBuildTree(int inorderLeft, int inorderRight, int postorderLeft, int postorderRight) {

        if (inorderLeft > inorderRight || postorderLeft > postorderRight) return null;

        TreeNode root = new TreeNode(postOrder[postorderRight]);                        // 注意这里用的是 后续遍历的根节点
        Integer inorderIndex = indexMap.get(postOrder[postorderRight]);

        root.left = myBuildTree(inorderLeft, inorderIndex - 1, postorderLeft, postorderLeft + (inorderIndex - inorderLeft) - 1);  // 左子树
        root.right = myBuildTree(inorderIndex + 1, inorderRight, postorderLeft + (inorderIndex - inorderLeft), postorderRight - 1); // 右子树
        return root;
    }
}
